package com.atwulidun.stack;

import java.util.*;

public class PolandNotation {
    public static void main(String[] args) {
//        // 定义一个后缀表达式
//        String suffixExpression = "30 4 + 5 * 6 -";
//        // 获取后缀List<String>
//        List<String> suffixList = toSuffixExpressionListString(suffixExpression);
//        System.out.println(suffixList);

        // 定义一个中缀表达式
//        String infixExpression = "(3*(12-2*(8-1*3)))/((33-32)*(20-18))";//3
        String infixExpression = "-100-(-60/2)";
        // 获取中缀List<String>
        List<String> infixList = toInfixExpressionListString(infixExpression);
        System.out.println("中缀List<String>为：" + infixList);
        // 由中缀List<String>转换为后缀List<String>
        List<String> suffixList = parseInfixToSuffixExpressionListString(infixList);
        System.out.println("后缀List<String>为：" + suffixList);
        // 根据List<String>获取表达式的计算结果
        int res = calculate(suffixList);
        System.out.println("表达式的计算结果为：" + res);
    }

    // 以下一共有五个方法，四个基本转换计算方法，一个返回优先级大小的方法
    // 将逆波兰表达式转换为List<String>的方法
    public static List<String> toSuffixExpressionListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        return new ArrayList<>(Arrays.asList(split));
    }

    // 将中缀表达式转换为List<String>的方法(考虑有负数的情况)
    public static List<String> toInfixExpressionListString(String infix) {
        // 一、先定义一个list
        List<String> list = new ArrayList<>();
        // 二、跟之前扫描一样，定义三个变量，再加一个boolean型变量来对负数进行标记
        int index = 0;
        char ch;
        String str = "";
        boolean flag = false;// 当扫描到有负数时，把flag置为true
        // 三、接下来对infix进行扫描
        while (index < infix.length()) {
            // 若扫描到的字符不为数字，则直接入list即可，注意栈内的元素是String类型，记得将char转为String
            if ((ch = infix.charAt(index)) < 48 || (ch = infix.charAt(index)) > 57) {
                // -6/3等价于(0-6)/3，多了'(''0'
                // (-3 + 2)等价于((0-3)+2)
                if (index == 0 && ch == '-' || index !=0 && infix.charAt(index - 1) == '(' && ch == '-') {
                    list.add('(' + "");
                    list.add(0 + "");
                    list.add(ch + "");
                    // 同时把flag置为true
                    flag = true;
                } else {
                    list.add(ch + "");
                }
                index++;// 这句话容易漏掉！！！！！！！
            } else {
                // 对多位数字进行拼接
                while (index < infix.length() && (ch = infix.charAt(index)) >= 48 && (ch = infix.charAt(index)) <= 57) {
                    str += ch;
                    index++;// 这句话容易漏掉！！！！！！
                }
                // 拼接好后将str加入到list中
                list.add(str);
                // 如果前面有负数，则要对标志位进行判断
                if (flag) {
                    list.add(')' + "");
                    // 记得对flag进行重置
                    flag = false;
                }
                // 最最最最最容易漏掉的一步，就是对str进行清空！！！！！
                str = "";
            }
        }
        return list;
    }

    // 将中缀List<String>转换为后缀List<String>的方法
    public static List<String> parseInfixToSuffixExpressionListString(List<String> infix) {
        // 一、首先创建一个栈和一个List<String>
        Deque<String> stack = new ArrayDeque<>();// 用来存放运算符
        List<String> list = new ArrayList<>();// 用来存放中间元素
        // 二、因为是List<String> infix，故用增强型的for循环来扫描(如果是字符串String的话用while来扫描)
        for (String s : infix) {
            // 如果匹配数字，则直接加入list
            if (s.matches("\\d+")) {
                list.add(s);
            } else {
                // 如果是运算符，则分情况讨论
                if (stack.isEmpty() || s.equals("(")) {
                    stack.push(s);
                } else if (s.equals(")")) {
                    while (!(stack.peek().equals("("))) {
                        list.add(stack.pop());
                    }
                    stack.pop();
                } else {
                    // 该种情况为：stack不为空，并且运算符为'+''-''*''/'，需要对优先级进行判断，又分为两种情况
                    if (priority(s) <= priority(stack.peek())) {
                        list.add(stack.pop());
                        stack.push(s);
                    } else {
                        stack.push(s);
                    }
                }
            }
        }
        // 三、for循环结束，需要把stack里面所有的符号都依次加入到list中
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    // 根据List<String>来对表达式的值进行计算
    public static int calculate(List<String> list) {
        // 创建一个栈
        Deque<String> stack = new ArrayDeque<>();
        // 对List<String>进行遍历，如果是数字就直接入栈；如果是操作符则从栈内弹出两个数进行计算，再将结果入栈
        for (String s : list) {
            // 匹配多位整数
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                char ch = s.charAt(0);
                int res;
                switch (ch) {
                    case '+':
                        res = num2 + num1;
                        break;
                    case '-':
                        res = num2 - num1;
                        break;
                    case '*':
                        res = num2 * num1;
                        break;
                    case '/':
                        res = num2 / num1;
                        break;
                    default:
                        throw new RuntimeException("非法的运算符！");
                }
                // 计算完后要将结果入栈，注意栈内存储的数据类型为String
                stack.push(res + "");
            }
        }
        // 全部遍历完，则留在栈内的最后一个元素即为最终的结果
        return Integer.parseInt(stack.pop());
    }

    // 返回优先级大小的方法，数字越大优先级越高
    public static int priority(String oper) {
        if (oper.equals("*") || oper.equals("/")) {
            return 1;
        } else if (oper.equals("+") || oper.equals("-")) {
            return 0;
        } else {
            return -1;// '('的优先级最低
        }
    }
}

